package leetcode.code0473;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.HelpDebug;

//
public class Solution implements IDebug {

	public boolean makesquare(int[] matchsticks) {
		int total = 0;
		for (int num : matchsticks) {
			total += num;
		}
		if (total % 4 != 0) {
			// 除不开直接凉
			return false;
		}
		int aim = total / 4;
		int len = matchsticks.length;
		int limit = 1 << len;
		// 哪些组合是不行的。
		Boolean[] dp = new Boolean[limit];
		// 数据，凑齐4个棍子，每个棍子的长度，还有哪些能用，目前凑了多少，缓存
		return this.find(matchsticks, 4, aim, limit - 1, 0, dp);
	}

	private boolean find(int[] matchsticks, int num, int aim, int limit, int sum, Boolean[] dp) {
		if (num == 0) {
			return limit == 0;
		}
		if (dp[limit] != null) {
			return dp[limit];
		}
		int len = matchsticks.length;
		for (int i = 0; i < len; i++) {
			int index = 1 << i;
			// 这个位置能用
			if ((limit & index) != 0) {
				int tyr = matchsticks[i];
				// 凑齐一个棍子
				if (sum + tyr == aim) {
					// num - 1棍子少一个，limit-index这个棍子不能用了，从0开始继续找
					if (this.find(matchsticks, num - 1, aim, limit - index, 0, dp)) {
						return true;
					}
				} else if (sum + tyr < aim) {
					// 不够aim棍子没少，limit-index这个棍子不能用了，sum + tyr累计找到的数量
					if (this.find(matchsticks, num, aim, limit - index, sum + tyr, dp)) {
						return true;
					}
				}
			}
		}
		dp[limit] = false;
		return false;
	}

//作者：wa-pian-d
//链接：https://leetcode.cn/problems/matchsticks-to-square/solution/473-huo-chai-pin-zheng-fang-xing-java-by-n7q7/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.makesquare(HelpDebug.str2array3("[5,5,5,5,4,4,4,4,3,3,3,3]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(false, this.makesquare(HelpDebug.str2array3("[5,5,5,5,16,4,4,4,4,4,3,3,3,3,4]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
